truct Node {
    int count = 1;
    int time = 0;
    int key = 0, val = 0;
    Node() {};
    Node(int key_, int val_, int time_) : key(key_), val(val_), time(time_){} 
};

bool comp(Node* n1, Node* n2) {
    return n1->count == n2->count ? n1->time < n2->time : n1->count < n2->count;
}
bool (*fn)(Node* n1, Node* n2) = comp;


class LFUCache {
public:
    unordered_map<int, Node*> book;
    bool (*fn)(Node*, Node*) = comp;
    set<Node*, bool(*)(Node*, Node*)> cset;
    int capacity;
    int size = 0;
    int time = 0;
    void Print() {
        for (auto ele : cset) {
            cout << ele->key << ":" << ele->val << ":" << ele->count << ":" << ele->time << endl;
        }
        cout << "---" << endl;
    }
    LFUCache(int capacity_) : capacity(capacity_), cset(fn){
    }
    
    int get(int key) {
        int result = -1;
        if (book.find(key) != book.end()) {
            Node* node = book[key];
            cset.erase(node);
            node->time = time++;
            node->count += 1;
            cset.insert(node);
            result = node->val;
        }
        return result;
    }
    
    void put(int key, int value) {
        if (book.find(key) == book.end()) {
            if (size == capacity) {
                Node* node = *cset.begin();
                cset.erase(node);
                book.erase(node->key);
                size--;
            }
            Node* node = new Node(key, value, time++);
            book.insert({key, node});
            cset.insert(node);
            size++;
        }
        else {
            book[key]->val = value;
            cset.erase(book[key]);
            book[key]->count++;
            book[key]->time = time++;
            cset.insert(book[key]);
        }
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
